package 贪心算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 解题思路：
 * 1、记录每个字母在S中最后出现的下标
 * 2、从下标0开始尝试分段，左边界left是0
 * 3、“同一个字母必须在同一片段中”,所以初始right是该段首字母最后出现的位置
 * 4、动态遍历left到right，如果有字符最后出现的下标大于right，更新right
 * 5、遍历完成后，一个分段就生成了。计数区间长度，更新left = right + 1，转3继续。
 *

 */
public class 划分字母区间_763 {
    public static void main(String[] args) {
        String s="caedbdedda";
      System.out.println(new 划分字母区间_763().partitionLabels(s)) ;

    }

    public  List<Integer> partitionLabels(String S) {

        Map<Character,Integer> map=new HashMap<>();//用来存放每个元素的最后出现的位置下标

        char[] s = S.toCharArray();//toCharArray() 方法将字符串转换为字符数组。

        for (int i = 0; i <s.length ; i++) {
                map.put(s[i],i);//一轮遍历完了以后，元素最后一次出现的位置被存放到了map中。
        }

        int left=0;
        int right=map.get(s[0]);//right被初始化为第一个元素最后出现的位置

        List<Integer> result=new ArrayList<>();

        while (left<=right){//之所要等号，是考虑到数组的第一个元素有且仅有一个，这样left和right都是0，如果没有等号就进不了循环
            for (int i = left; i <right ; i++) {
                if (map.get(s[i])>right){//如果在初始的left--right区间内，有元素的最后出现位置大于初始的right，则更新right。
                    right=map.get(s[i]);
                }
            }
            result.add(right-left+1);//第1、2、3、4...个区间的长度

            left=right+1;//上面的循环结束后，求出了第一个区间，第二个区间的left为上一轮得到的right+1，这轮的初始right为map.get(right+1)

            if (left-1==(s.length-1)){//如果已经到了最后一个区间了：那么上轮循环结束后的right+1就是s的length。 即这一轮的left-1==上一轮的right ==s.length-1
                right=left-1; //让right比left小1 跳出循环
            }else{
                right=map.get(s[left]);
            }






        }


        return result;
    }
}
